# 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
#  对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
#  示例 1：
# 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
# 输出：4
# 解释：最长递增路径为 [1, 2, 6, 9]。
#
#  示例 2：
# 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
# 输出：4
# 解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
#
#  示例 3：
# 输入：matrix = [[1]]
# 输出：1
from collections import deque
from typing import List


class Solution:
    def longestIncreasingPath3(self, matrix: List[List[int]]) -> int:
        pass

    def longestIncreasingPath2(self, matrix: List[List[int]]) -> int:
        """
        解法二：拓扑排序(求拓扑排序的最大层数)
        从matrix中抽象出图的规则:
            一个节点的上下左右如果有比这个节点小的，则说明有一条从邻接点(上下左右)指向自己，即它的入度
        :param matrix:
        :return:
        """
        rows, columns = len(matrix), len(matrix[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        indegrees = [[0] * columns for _ in range(rows)]
        res = 0
        for i in range(rows):  # 初始化每个点的入度
            for j in range(columns):
                for dx, dy in directions:
                    newRow, newCol = i + dx, j + dy
                    if 0 <= newRow < rows and 0 <= newCol < columns and matrix[newRow][newCol] < matrix[i][j]:
                        indegrees[i][j] += 1
        q = deque()
        for i in range(rows):  # 将入度为 0 的放入到队列中
            for j in range(columns):
                if indegrees[i][j] == 0:
                    q.append((i, j))

        while q:
            layerSize = len(q)
            res += 1
            while layerSize:
                x, y = q.popleft()
                for dx, dy in directions:
                    newX, newY = x + dx, y + dy
                    if 0 <= newX < rows and 0 <= newY < columns and matrix[x][y] < matrix[newX][newY]:
                        indegrees[newX][newY] -= 1
                        if indegrees[newX][newY] == 0:
                            q.append((newX, newY))
                layerSize -= 1

        return res

    def longestIncreasingPath1(self, matrix: List[List[int]]) -> int:
        """
        解法一：DFS遍历计算以当前节点为开始节点的最大递增路径长度
        :param matrix:
        :return:
        """
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        tmpMaxLen, res = 0, 0
        m, n = len(matrix), len(matrix[0])

        def dfs(row: int, col: int) -> int:  # 暴力DFS搜索
            tmpResult = 1
            for x, y in directions:
                newRow, newCol = row + x, col + y
                if 0 <= newRow < m and 0 <= newCol < n and matrix[row][col] < matrix[newRow][newCol]:
                    tmpResult = max(dfs(newRow, newCol) + 1, tmpResult)
            return tmpResult

        tmpResMatrix = [[-1] * n for _ in range(m)]  # 记录从(i, j)开始的最大递增长度

        def dfs2(row: int, col: int) -> int:  # 将计算过的节点的最大递增路径使用数组记录下来，后面使用到了直接查询即可
            if tmpResMatrix[row][col] != -1:
                return tmpResMatrix[row][col]
            tmpResult = 1
            for x, y in directions:
                newRow, newCol = row + x, col + y
                if 0 <= newRow < m and 0 <= newCol < n and matrix[row][col] < matrix[newRow][newCol]:
                    tmpResult = max(dfs2(newRow, newCol) + 1, tmpResult)
            tmpResMatrix[row][col] = tmpResult
            return tmpResult

        for i in range(m):
            for j in range(n):
                res = max(res, dfs2(i, j))
        return res

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        return self.longestIncreasingPath2(matrix)


if __name__ == "__main__":
    matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
    print(Solution().longestIncreasingPath(matrix))
